package 回溯.不熟;

import java.util.Arrays;
import java.util.Date;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 完成任务的最少工作时间段1986.java
 * @createTime 2023年04月14日 16:22:00
 */
public class 完成任务的最少工作时间段1986 {

	public static void main(String[] args) {
	/*	System.out.println(new Date(1681747200000L));
		System.out.println(new Date(1680591853135L));
		System.out.println(new Date(1680591852135L).after(new Date(1680591851135L)));
		System.out.println( 4 % 100 == 0 ? 4 / 100 : (4 / 100 + 1));*/
		//System.out.println(minSessions(new int[] {1, 2, 3}, 3));
	}

	/*static int minWorkTime = Integer.MAX_VALUE;

	public static int minSessions(int[] tasks, int sessionTime) {
		//从小到大拍一次
		Arrays.sort(tasks);
		//然后倒序一次
		reverseArray(tasks);
		boolean[] used = new boolean[tasks.length];
		//进行回溯
		backTrace(tasks, used, 0, tasks.length, sessionTime, 0, sessionTime, tasks.length);
		return minWorkTime;
	}

	public static void backTrace(int[] big2Small, boolean[] used, int curIndex, int length, int left, int workTime,
								 int sessionTime, int workLeft) {
		//结束条件，工作完成
		if (workLeft == 0) {
			minWorkTime = Math.min(workTime, minWorkTime);
			return;
		}
		//先算最大的然后算最小的
		for (int i = 0; i < length; i++) {
			//工作已经做了，下一个
			if (used[i]) {
				continue;
			}
			used[i] = true;
			workLeft-=1;
			//如果剩余时间不够，则下一个
			if (left <= big2Small[i]) {
				if (used[i-1]){
					backTrace(big2Small, used, i + 1, length, sessionTime, workTime + 2, sessionTime, workLeft);
				}else {
					backTrace(big2Small, used, i + 1, length, sessionTime, workTime + 1, sessionTime, workLeft);
				}
			} else {
				backTrace(big2Small, used, i + 1, length, left - big2Small[i], workTime, sessionTime, workLeft );
			}
			workLeft+=1;
			used[i] = false;
		}
	}

	public static void reverseArray(int[] arr) {
		int start = 0;
		int end = arr.length - 1;
		while (start < end) {
			int temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
			start++;
			end--;
		}
	}*/

	/**
	 * 首先，计算数组 tasks 的总和 totalSum，这个值在后续的回溯过程中会被用到。
	 * 创建一个全局变量 minSessions，用于记录完成所有任务所需的最少时间段数，初始化为一个较大的值，比如 totalSum。
	 * 创建一个长度为 totalSum 的一维数组 times，用于记录每个时间段已经使用的时间，初始值都为 0。
	 * 从 1 个时间段开始尝试，然后逐步增加时间段数，调用回溯函数 backtrack 来搜索所有可能的任务安排方式。
	 * 在回溯函数 backtrack 中，从左到右遍历 tasks 数组，并尝试将当前任务安排在不同的时间段内。
	 * 如果当前时间段剩余时间足够执行当前任务，则将任务安排在该时间段内，并继续递归地向下搜索。
	 * 如果当前时间段剩余时间不足以执行当前任务，则尝试在下一个时间段安排当前任务，并继续递归地向下搜索。
	 * 在回溯过程中，记录完成任务所需的时间段数 count，并根据 count 更新全局变量 minSessions 的值，以找到最少的时间段数。
	 * 回溯函数结束后，minSessions 即为完成所有任务所需的最少时间段数
	 */

	public class Solution {
		private int minSessions;

		public int minSessions(int[] tasks, int sessionTime) {
			int totalSum = 0;
			for (int task : tasks) {
				totalSum += task;
			}
			minSessions = totalSum;
			int[] times = new int[totalSum];
			backtrack(tasks, sessionTime, times, 0, 0);
			return minSessions;
		}

		private void backtrack(int[] tasks, int sessionTime, int[] times, int index, int sessions) {
			if (index == tasks.length) {
				minSessions = Math.min(minSessions, sessions);
				return;
			}

			for (int i = 0; i < sessions; i++) {
				if (times[i] + tasks[index] <= sessionTime) {
					times[i] += tasks[index];
					backtrack(tasks, sessionTime, times, index + 1, sessions);
					times[i] -= tasks[index];
				}
			}

			times[sessions] = tasks[index];
			backtrack(tasks, sessionTime, times, index + 1, sessions + 1);
			times[sessions] = 0;
		}
	}

	int res;
	int maxSessionTime;
	int[] tasks;
	int[] sessions;

	public int minSessions(int[] tasks, int sessionTime) {
		this.res = tasks.length;
		this.maxSessionTime = sessionTime;
		this.tasks = tasks;
		this.sessions = new int[tasks.length];
		backTracking(0, 0);
		return res;
	}

	public void backTracking(int taskId, int sessionCount) {
		// 减枝,如果当前所需工作时间片，已大于已有结果集，不可能还有更少的
		if (sessionCount > res) {
			return;
		}

		//做完最后一个任务
		if (taskId == tasks.length) {
			res = Math.min(res, sessionCount);
			return;
		}

		for (int i = 0; i < sessionCount; i++) {
			//每个sessionCount，代表一个工作时间段
			//放入当前task到当前的工作时间段
			if (sessions[i] + tasks[taskId] <= maxSessionTime) {
				sessions[i] += tasks[taskId];
				backTracking(taskId + 1, sessionCount);
				sessions[i] -= tasks[taskId];
			}
		}

		//如果当前task + 之前task  已经超过最大连续工作时间maxSessionTime，新起一个sessionCount，继续回溯
		sessions[sessionCount] += tasks[taskId];
		backTracking(taskId + 1, sessionCount + 1);
		sessions[sessionCount] -= tasks[taskId];

	}
}
